zk-SNARKs Overview
zk-SNARKsとは
Zero-Knowledge Succinct Non-Interactive Argument of Knowledge
proverとverifier間で対話を必要としないゼロ知識証明の亜種。
Zero-knowledge
ゼロ知識証明
数学的な命題が真であることを伝えるのに、「真であること」以外何の知識も伝えずに証明する手法
4+s1+s2=15となるinputのs1、s2を明らかにせずにoutputが正しいことを証明する
s1とs2として何が入力されたかは分からないけど、上記の式はちゃんと満たしていることが証明される。
Succinct
proofの検証が数ミリ秒（とか）で可能
Non-interactive
ProverとVerifierでの非対話性
「SNARKs」の名付け論文
From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again: https://eprint.iacr.org/2011/443.pdf
ベースプロトコルはピノキオプロトコル
Pinocchio: https://eprint.iacr.org/2013/279.pdf
Zcashが主導で開発
Txのvalid or notを送信するだけの秘匿化チェーン
zk-SNARKs on Ethereum
Byzantiumでbn256Add, bn256ScalarMul, bn256Pairingの追加
EIP 1108: Reduce alt_bn128 precompile gas costs: https://eips.ethereum.org/EIPS/eip-1108
https://gyazo.com/b48904355602c70a145f355cb004bc1a
block.number >= CONSTANTINOPLE_FORK_BLKNUM
gethにおけるbn256演算をcloudflareのライブラリに変更したら改善
https://github.com/cloudflare/bn256
parityにおけるbn256ライブラリ
https://github.com/paritytech/bn/pull/9
bnベンチマーク：https://gist.github.com/pdyraga/4649b74436940a01e8221d85e80bfeef
Core Devs 9/28/2018でのEIP1108: https://github.com/ethereum/pm/issues/58
OK。testing頑張っていき。
https://github.com/ethereum/EIPs/issues/1187
https://github.com/ethereum/wiki/wiki/Byzantium-Hard-Fork-changes
https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L57-L59
https://github.com/barryWhiteHat/roll_up/blob/master/contracts/Pairing.sol#L45
code:add.sol
/// @return the sum of two points of G1
function add(G1Point p1, G1Point p2) internal returns (G1Point r) {
uint4 memory input;
input0 = p1.X;
input1 = p1.Y;
input2 = p2.X;
input3 = p2.Y;
bool success;
assembly {
success := call(sub(gas, 2000), 6, 0, input, 0xc0, r, 0x60)
// Use "invalid" to make gas estimation work
switch success case 0 { invalid }
}
require(success);
call(g, a, v, in, insize, out, outsize)
SNARKsを用いたoffchain computationによるスケーリングがホットトピック
メリット
proofのサイズが小さい
デメリット
trusted setup
Provingの計算コスト
20Txの署名検証を伴うTx集約でlaptopで30秒くらい
主にハッシュ関数が厳しい
MiMChash関数: https://github.com/zcash/zcash/issues/2233
~800 constraints per hash
署名検証のためのembdded Edwards curve(jubjub): https://z.cash/technology/jubjub.html
体のbitあたり約4.2 constarins
署名検証 ~2000 contraints
DIZKによる分散計算が最近提案 : https://eprint.iacr.org/2018/691.pdf
仕組みの概略
https://gyazo.com/2d5a21fcdad1923822cc48f01799c97b
https://gyazo.com/83129a24421586ec258da66b69a6a390
実際のユースケース
マークルツリーを使って複数のスロットの状態遷移を１つのトランザクションで起こすsnarks provingをオンチェーンでverifyすることでスケーリング。
https://gyazo.com/7b09fabe2e902296d59ccaea9a9bb35b
実装手段は大きく分けて2通りの考え方
vitalik model
zk-SNARKsを用いたオンチェーンスケーリング
Txデータもオンチェーンに送信することでデータの可用性を保証
マークルリーフもコントラクトでトラッキングすることになるのでユーザーは全てのbalanceデータなどを参照できる
ただ、単純にTxをsnarks provingのinputに使ってしまうとオンチェーンのverifyでも全てのtxをinputにしなくてはならず、それごとにecmulを行うことになりgasがやばくなってしまう。
on-chain scaling
roll_up model : https://github.com/barryWhiteHat/roll_up
複数のトランザクションを集約し１つのトランザクションをオンチェーンに送信。
snarkが署名Txにより書き換えられるマークルリーフの正当性を保証
Txを送信せずマークルルートのみをトラッキングするのではユーザーにとってデータは可用ではない。
そのマークルルート算出に用いられたTxの正当性と署名によるスロットの保証、Txによる状態遷移など、マークルルート計算の正当性はsnarkで保証されている。
最初のiterationであればスマートコントラクトからマークルルートをinputとして取得
メッセージとマッチするマークルリーフを探す
トランザクションの構成
公開鍵(x. y)
メッセージ：更新前のリーフと更新後のリーフのハッシュ値
署名(r, s)
マークルリーフは公開鍵を管理
トランザクションの公開鍵とマークルリーフの公開鍵が一致するか検証
署名が正しいか検証
新しいリーフと置き換え、新しいマークルルートを計算
これをsnarkに含められた全てのトランザクションに対して行うまで繰り返す
スケーラビリティ
verify : ~600,000gas
１つのリーフupdateに対するevent発火: 1840 gas
plasma snapp
batch auction
https://gyazo.com/188eb31c759f5c5ef6b3b8d9293a4923
0x型のDEXも同様の考え方でTx集約してsnarks provingすればスケールする。
十分な流動性がないとスケールしない
逆にprove time分遅くなる
リレイヤーの負担が増す。
proving 計算コスト
coda protocol
開発ツール
ライブラリ
libsnark: SCIPR Labが開発してるc++ライブラリ
SCIPR Lab: http://www.scipr-lab.org/
zcashにも使われている
bellman: zCash（所属の一人）が開発してるrustライブラリ
イーサ向け
Zokrates: https://github.com/JacobEberhardt/ZoKrates
code:add.code
def main(a, b, c):
return a + b + c
ethsnarks : https://github.com/HarryR/ethsnarks
harry先生
Groth16を用いた最適化
webassemblyによるブラウザ上での証明
iden3
compiler: https://github.com/iden3/circom
snarks: https://github.com/iden3/zksnark
coda
https://youtu.be/h0PUVR0s6Vg
詳しい仕組み
zk-SNARKs | setup-prooving-verifying
#zk-SNARKs #数学 #ゼロ知識証明 #暗号学
勉強会コメント
shuntak.icon > DIZK論文で提案されている分散証明
従来の証明生成システムはモノリシックだったが、提案手法で分散することにより証明が100倍早くなったとのこと
https://eprint.iacr.org/2018/691.pdf
yudetamago.icon > zk-SNARKsの読み方は「ズィーケースナークス？」